JGS 迭代法

JGS 迭代法是 Jacobi 迭代法的一种改进方法，虽然 Jacobi 迭代法的迭代公式 ${\mathit{x}}^{\mathbf{(}\mathit{k}\mathbf{+}\mathbf{1}\mathbf{)}}=B_J{\mathit{x}}^{\mathbf{(}\mathit{k}\mathbf{)}}+{\mathit{g}}_J$ 看起来可以一步就解出 ${\mathit{x}}^{\mathbf{(}\mathit{k}\mathbf{+}\mathbf{1}\mathbf{)}}$，但是在实际计算中，还是需要一个一个地解方程。

JGS 迭代法的改进之处在于，它在每次迭代中每解一个方程，就代入更新后的变量来计算下一个方程，这样可以加快迭代的收敛速度。

迭代公式

这里省略方程式推导过程

方程式写起来比较麻烦，原理是先解出方程组中的一个方程，然后用已有的解来更新下一个方程中的系数，以此类推，这样就可以逐个解出所有的变量。

从推导后的方程式可以看出，JGS 迭代法的迭代矩阵本身没变，只是对角线以下的部分（$B_1$）与新的 ${\mathit{x}}^{\mathbf{(}\mathit{k}\mathbf{+}\mathbf{1}\mathbf{)}}$ 相乘，对角线以上的部分（$B_2$）与旧的 ${\mathit{x}}^{\mathbf{(}\mathit{k}\mathbf{)}}$ 相乘。因此就有下面的 JGS 迭代公式。

和 Jacobi 迭代法类似，由

• 系数矩阵 $A$：

  $$\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]$$
  由系数矩阵 $A$ 可以拆开得到...

  • 下三角矩阵 $L$：$$\left[\begin{array}{cccc}0& & & \\ a_{21}& 0& & \\ ⋮& ⋮& \ddots & \\ a_{n1}& a_{n2}& \cdots & 0\end{array}\right]$$
  • 上三角矩阵 $U$：$$\left[\begin{array}{cccc}0& a_{12}& \cdots & a_{1n}\\ & 0& \cdots & a_{2n}\\ & & \ddots & ⋮\\ & & & 0\end{array}\right]$$
  • 对角矩阵 $D$：$$\left[\begin{array}{cccc}{a}_{11}& & & \\ & a_{22}& & \\ & & \ddots & \\ & & & a_{nn}\end{array}\right]$$

  注意

  此处的 $L$ 和 $U$ 与 矩阵的 LU 分解 中的 $L$ 和 $U$ 不是同个概念！

• 常数向量 $\mathit{b}$：

  $$\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right]$$

可以得出：

• 迭代矩阵 $B_J=-D^{-1}(L+U)$：

  $$\left[\begin{array}{cccc}0& -\frac{a_{12}}{a_{11}}& \cdots & -\frac{a_{1n}}{a_{11}}\\ -\frac{a_{21}}{a_{22}}& 0& \cdots & -\frac{a_{2n}}{a_{22}}\\ ⋮& ⋮& & ⋮\\ -\frac{a_{n1}}{a_{nn}}& -\frac{a_{n2}}{a_{nn}}& \cdots & 0\end{array}\right]$$

  其中：

  $$B_1=-D^{-1}L=\left[\begin{array}{cccc}0& & & \\ -\frac{a_{21}}{a_{22}}& 0& & \\ ⋮& ⋮& \ddots & \\ -\frac{a_{n1}}{a_{nn}}& -\frac{a_{n2}}{a_{nn}}& \cdots & 0\end{array}\right]$$$$B_2=-D^{-1}U=\left[\begin{array}{cccc}0& -\frac{a_{12}}{a_{11}}& \cdots & -\frac{a_{1n}}{a_{11}}\\ & 0& \cdots & -\frac{a_{2n}}{a_{22}}\\ & & \ddots & ⋮\\ & & & 0\end{array}\right]$$

• 迭代常数向量 ${\mathit{g}}_J=D^{-1}\mathit{b}$：

  $$\left[\begin{array}{c}\frac{b_1}{a_{11}}\\ \frac{b_2}{a_{22}}\\ ⋮\\ \frac{b_n}{a_{nn}}\end{array}\right]$$

因此，由上述推导过程，JGS 迭代法的迭代公式是：

$${\mathit{x}}^{(k+1)}=B_1{\mathit{x}}^{(k+1)}+B_2{\mathit{x}}^{(k)}+{\mathit{g}}_J$$

等效为简单迭代法

JGS 迭代法的迭代公式 ${\mathit{x}}^{(k+1)}=B_1{\mathit{x}}^{(k+1)}+B_2{\mathit{x}}^{(k)}+{\mathit{g}}_J$ 并不能直接等效为简单迭代法 $\mathit{x}=B\mathit{x}+\mathit{g}$ 的形式，因为等式的左右两边都有 ${\mathit{x}}^{(k+1)}$。

因此，代入 $B_1=-D^{-1}L$、$B_2=-D^{-1}U$ 并整理等式，将 ${\mathit{x}}^{(k+1)}$ 移到左边，得到：

$${\mathit{x}}^{(k+1)}=-(D+L{)}^{-1}U{\mathit{x}}^{(k)}+(D+L{)}^{-1}\mathit{b}$$

即，

迭代矩阵 $B_{JGS}$：

$$B_{JGS}=-(D+L{)}^{-1}U$$

迭代向量 $g_{JGS}$：

$${\mathit{g}}_{JGS}=(D+L{)}^{-1}\mathit{b}$$

则 JGS 迭代法等效为简单迭代法的迭代公式 为：

$${\mathit{x}}^{(k+1)}=B_{JGS}{\mathit{x}}^{(k)}+g_{JGS}$$

收敛性判断

充分条件

满足以下条件之一，JGS 迭代法对任意初始向量一定收敛：

1. 原系数矩阵 $A$ 严格对角占优。
2. 原系数矩阵 $A$ 对称正定。
3. 迭代矩阵 $B_{JGS}$ 的任一种 矩阵范数 $\le 1$。

充要条件

迭代矩阵 $B_{JGS}$ 的谱半径 $<1$。

与 Jacobi 迭代法收敛性的关系

除非原系数矩阵 $A$ 严格对角占优，否则 JGS 迭代法的收敛性与 Jacobi 迭代法无必然联系。